import java.util.Arrays;

/**
 * @author 何泽
 * @version 1.0
 */
//KMP算法
public class a {
    public static void main(String[] args) {
        String str = "ABCABCAABCABCD";
        String pattern = "ABCABCD";
        int []next = new int[pattern.length()];
        getnext(pattern.toCharArray(), next);
        int res = search(str.toCharArray(), pattern.toCharArray(), next);
        System.out.println(Arrays.toString(next));
        System.out.println(res);
    }
    static int search(char []str, char[] pattern, int[] next){
        int i = 0, j = 0;
        while (i < str.length && j < pattern.length){
            if (j == -1 || str[i] == pattern[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if (j == pattern.length){
            return i - j;
        }else{
            return  -1;
        }
    }
    static void getnext(char []pattern, int[] next){
        next[0] = -1;
        int i = 0, j = -1;

        while (i < pattern.length){
            if (j == -1){
                i++;
                j++;
            }else if(pattern[i] == pattern[j]){
                i++;j++;
                next[i] = j;
            }else{
                j = next[j];
            }
        }
    }
}
